package info.leetcode.answer.Link.foreach;

import java.util.Stack;

public class Flatten {

    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    // [1,2,3,7,8,11,12,9,10,4,5,6]
    Node temp = null ;
    public Node flatten(Node head) {
        if (head == null){
            return  head ;
        }
        if (head.child !=null){
            Node child = flatten(head.child);
            Node mark = temp ;
            Node next = flatten(head.next);
            head.next = child ;
            child.prev = head;
            head.child = null ;
            if (next == null){
                return head ;
            }
            mark.next = next;
            next.prev = mark;
            return head ;
        }
        if (head.next!=null){
            Node next = flatten(head.next);
            head.next = next;
            next.prev = head ;
        }
        if (head.next == null){
            temp = head ;
        }
        return head;
    }
}
